# 题目2：机制的外卖员
# 外卖员每天在大厦中送外卖，大厦共有L层（0<L<=10^5），当他处于第N层楼时，可以每分钟通过步行梯向上达到N+1层，或向下达到N-1层，
# 或者乘坐电梯达到2*N层。给定他所处位置N，以及外卖配送的目的楼层M，计算他送达的最短时间
# 1
# 2
# 输入：5 17
# 输出：4
#
# 直觉是动态规划, 子问题拆解碰到问题:
# 从第N层到第i层, 方式只可能有三条:
# 1)先到第i-1层, 再上一层, 即d[i-1]+1
# 2)先到i+1层, 再下一层, 即d[i+1]+1
# 3)如果i是偶数, 还可能是从i/2层坐电梯上来, 即d[i/2]+1
# 但这样d[i]依赖d[i+1]无法使用动态规划(d为最短路径函数)
#
# 下面证明方式2中到i+1层的方式一定是坐电梯直接到的, 否则一定不是最短路径:
# 要到i+1层同样只有两种方式:
# 1)从第i层上来, 不可能
# 快递员要到i层, 因此不可能是从i层走上来的, 除非傻了
# 2)从坐电梯到第i+1+k层走下来, k >= 0, k=0时不用走
# 2.1)如果i为偶数, k定为奇数, 总路程s1为: d[(i+1+k)/2]+1+(k+1)
# 而另一方面, 到第i/2层的最短路径一定小于等于先到d[i/2+(k+1)/2]再下楼到i/2层, 因为这是其中的一条路径
# 即, d[i/2] <= d[i/2+(k+1)/2] + (k+1)/2
# 因此先到i/2层再坐电梯到i层的路程s2有:
# s2 = d[i/2]+1 <= d[i/2+(k+1)/2]+1+(k+1)/2 <d[(i+1+k)/2]+1+(k+1) = s1
# 所以此时s1一定不是最短路径
# 2.2)如果i为奇数, k一定为偶数, 总路程s1为: d[(i+1+k)/2]+1+(k+1)
# 到(i+1)/2层的最短路径一定小于等于其中的一条: 到(i+1)/2+k/2层然后再走下楼
# 即: d[(i+1)/2] <= d[(i+1)/2+k/2]+k/2
# 因此因此先到(i+1)/2层再坐电梯到i+1层再到第i层的路程s2有:
# s2 = d[(i+1)/2] + 1 + 1 <= d[(i+1)/2+k/2]+k/2+1+1 <= d[(i+1+k)/2]+1+(k+1)=s1
# 当且仅当k=0时等号成立
# 2.3)综上, 最短路径中, 到i+1层然后下楼到i层只有一种情况, 即先坐电梯到i+1层然后走下来
#
# 因此子问题可以拆解为:
# 从第N层到第i层, 方式只可能有三条:
# 1)先到第i-1层, 再上一层, 即d[i-1]+1
# 2)如果i为奇数, 可能坐电梯到i+1层下楼到第i层, 即d[(i+1)/2]+1+1
# 3)如果i是偶数, 还可能是从i/2层坐电梯上来, 即d[i/2]+1
#
# 此时d[i]只依赖小于i的函数值, 可以使用动态规划

def get_path(transit: dict, n: int, m: int):
    """
    获取路径
    :param transit: 中转节点 如果从n到i需要经过j则有transit[i]=j
    :param n: 外卖员的起始楼层
    :param m: 外卖员的目标楼层
    :return: 路程
    """
    s = m
    path = []
    while s != n:
        path.insert(0, s)
        if s in transit:
            s = transit[s]
        else:
            s = n
    path.insert(0, n)
    return path


def road_plan(n: int, m: int):
    """
    路径规划
    :param n: 外卖员的起始楼层
    :param m: 外卖员的目标楼层
    :return: 路程消耗的时间(分钟), 路径
    """
    if n >= m:
        return n - m
    transit = {}
    # 第1,2,3,...,m, 为了索引方便前面加一个第0层
    d = [abs(n - i) for i in range(0, m + 1)]
    for i in range(n + 1, m + 1):
        s1 = d[i - 1] + 1
        if i % 2:
            s2 = d[(i + 1) // 2] + 1 + 1
        else:
            s2 = d[i // 2] + 1

        if s1 <= s2:
            transit[i] = i - 1
            d[i] = s1
        else:
            d[i] = s2
            transit[i] = (i + 1) // 2 if i % 2 else i // 2
    return d[m], get_path(transit, n, m)


dst1, path1 = road_plan(5, 17)
print(dst1, '->'.join([str(each) for each in path1]))
dst2, path2 = road_plan(3, 10)
print(dst2, '->'.join([str(each) for each in path2]))
